package class202205.demo20.demo19;

import java.util.*;

public class TopK {
    /**
     * 求数组中的前k个最小的元素
     * @param array  数组
     * @param k  前k个最小的元素
     * @return
     */

    public static int[] topK(int[] array,int k){
        //  1、建一个大根堆----k
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        // 2、遍历数组当中的元素，前k个元素放到队列当中
        for (int i = 0; i < array.length; i++) {
            //先存k个元素进去
            if (maxHeap.size() < k) {
                maxHeap.offer(array[i]);
            } else {
                //3、从第k+1个元素开始，每个元素和堆顶元素进行比较
                //先别着急出
                int top = maxHeap.peek();
                if (top > array[i]) {
                    //3.1比他大  先弹出
                    maxHeap.poll();
                    //3.2后存入
                    maxHeap.offer(array[i]);
                }
            }
        }
        int[] tmp = new int[k];
        //弹出来k个
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }
    public static void main1(String[] args) {
        int[] array = {54,3,66,95,24,52};
        int[] tmp = topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

    /**
     * 给定两个以 升序排列 的整数数组 nums1 和 nums2,以及一个整数 k。
     * 定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自 nums2。
     * 请找到和最小的 k个数对(u1,v1), (u2,v2) ... (uk,vk)。
     * 链接：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                if (maxHeap.size()<k){
                    List<Integer> tmpList = new ArrayList<>();
                    tmpList.add(nums1[i]);
                    tmpList.add(nums2[j]);
                    maxHeap.offer(tmpList);
                }else {
                    int top = maxHeap.peek().get(0)+maxHeap.peek().get(1);
                    if (top>nums1[i]+nums2[j]){
                        //先弹出再入
                        maxHeap.poll();
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList.add(nums1[i]);
                        tmpList.add(nums2[j]);
                        maxHeap.offer(tmpList);
                    }
                }
            }
        }
        //弹出来就可以了
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {54,3,66,95,24,52};
        int[] tmp = topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

}
